package _2022.hot100._240_搜索二维矩阵II;

/**
 * @author： YHSimon
 * @date： 2022-05-21 14:54
 */
public class Solution {

    // Z字型查找 5ms
    public boolean searchMatrix2(int[][] matrix,int target){
        int m=matrix.length,n=matrix[0].length;
        int x=0,y=n-1;
        while(x<m&&y>=0){
            if(matrix[x][y]==target){
                return true;
            }
            if(matrix[x][y]<target){
                x++;
            }else{
                y--;
            }
        }
        return false;
    }

    //二分法  5ms
    public boolean searchMatrix(int[][] matrix,int target){
        int r=matrix.length,c=matrix[0].length;
        boolean flag;
        for(int i=0;i<r;i++){
            if(matrix[i][0]<=target&&target<=matrix[i][c-1]){
                flag=binarySearch(matrix,i,target);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean binarySearch(int[][] matrix, int i, int target) {
        int left=0,right=matrix[0].length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(matrix[i][mid]==target){
                return true;
            }else if(matrix[i][mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return false;
    }
}
